'''
https://leetcode.cn/problems/binary-tree-longest-consecutive-sequence
https://leetcode.cn/problems/binary-tree-longest-consecutive-sequence-ii
'''
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        def f(root):
            if not root:
                return 0, 0
            l_with, l_without = f(root.left)
            r_with, r_without = f(root.right)
            with_cur = 1
            if root.left and root.val + 1 == root.left.val:
                with_cur = max(with_cur, l_with + 1)
            if root.right and root.val + 1 == root.right.val:
                with_cur = max(with_cur, r_with + 1)
            without_cur = max(l_with, r_with, l_without, r_without)
            return with_cur, without_cur

        return max(f(root))

    def longestConsecutive_ii(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root:
                return 0, 0, 0

            l_inc, l_dec, lmax = dfs(root.left)
            r_inc, r_dec, rmax = dfs(root.right)

            # 左树，右树，一条直线(自顶向下的，一路不走父节点) 包含左右节点
            inc_inline, dec_inline = 1, 1
            if root.left and root.left.val + 1 == root.val:
                inc_inline = max(l_inc + 1, inc_inline)
            if root.left and root.left.val - 1 == root.val:
                dec_inline = max(l_dec + 1, dec_inline)
            if root.right and root.right.val + 1 == root.val:
                inc_inline = max(r_inc + 1, inc_inline)
            if root.right and root.right.val - 1 == root.val:
                dec_inline = max(r_dec + 1, dec_inline)

            # 最大长度，可能直线，可能能是包含自己左右
            max_len = max(lmax, rmax, inc_inline + dec_inline - 1)
            return inc_inline, dec_inline, max_len

        return max(dfs(root))
